package sort

// CounterSort 计数排序
func CounterSort(arr []int) []int {
	max := arr[0]
	for _, val := range arr {
		if val > max {
			max = val
		}
	}

	counters := make([]int, max)
	for _, val := range arr {
		counters[val-1]++
	}

	var res []int
	for idx, val := range counters {
		if val == 0 {
			continue
		}

		for i := 0; i < val; i++ {
			res = append(res, idx+1)
		}
	}

	return res
}
